LeetCode 303. Range Sum Query - Immutable

Posted on | In

303. Range Sum Query - Immutable

题目描述

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

示例:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

解答

这道题比较简单，我们预计算一个数组c，数组里面的下标i存的是原数组下标0 - i之间所有的值的和。

当我们需要计算i - j之间所有的数之和的时候，只需要返回c[j] - c[i - 1] 就行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class NumArray {
public:
    NumArray(vector<int>& nums) {
    	int n = nums.size();
        vector<int> d(n,0);
        if (nums.size() > 0) 
        	d[0] = nums[0];
        for(int  i = 1; i < nums.size(); i++ ) {
        	d[i] = d[i - 1] +  nums[i];

        }
        c = d;
    }
    
    int sumRange(int i, int j) {

    	if (i == 0) {
    		return c[j];
    	}
        return c[j] - c[i - 1];
    }
private:
	vector<int> c;
};